3.4.7 Polynomial Division

In integer arithmetic, the expression p÷d=d⋅q+r gives the quotient q and remainder r upon division of p by d. (Using the quotient operator, q=p//d is the largest integer such that r is less than d.) A similar equation holds for polynomials: p(x)=d(x)⋅q(x)+r(x). Dividing both sides by d(x) gives p(x)÷d(x)=(d(x)⋅q(x)+r(x))÷d(x). The left side of this equation represents the input to the polynomial division transformation. The right side represents the transformed expression.

Polynomial division can be applied to a subject consisting of a division operator in which the dividend and divisor are both polynomial expressions with the same variable, the degree of the dividend is less than that of the divisor, and no exponent is less than zero. The subject is replaced by a division with the same divisor and a dividend expressed as a product of two polynomials, one of which is the divisor, summed with another polynomial representing the remainder.

For example, polynomial division applied to (x^3-2⋅x^2+4⋅x-2)÷(x^2-1) yields ((x^2-1)⋅(x-2)+(5⋅x-4))÷(x^2-1).

Polynomial division is useful in root finding. However, it is often just one step in a series of transformations.